package array;

/**
 * 在一排多米诺骨牌中，tops[i] 和 bottoms[i] 分别代表第 i 个多米诺骨牌的上半部分和下半部分。（一个多米诺是两个从 1 到 6 的数字同列平铺形成的 —— 该平铺的每一半上都有一个数字。）
 * 我们可以旋转第 i 张多米诺，使得 tops[i] 和 bottoms[i] 的值交换。
 * 返回能使 tops 中所有值或者 bottoms 中所有值都相同的最小旋转次数。
 * 如果无法做到，返回 -1.
 * <p>
 * 示例 1：
 * 输入：tops = [2,1,2,4,2,2], bottoms = [5,2,6,2,3,2]
 * 输出：2
 * 解释：
 * 图一表示：在我们旋转之前， tops 和 bottoms 给出的多米诺牌。
 * 如果我们旋转第二个和第四个多米诺骨牌，我们可以使上面一行中的每个值都等于 2，如图二所示。
 * <p>
 * 示例 2：
 * 输入：tops = [3,5,1,2,3], bottoms = [3,6,3,3,4]
 * 输出：-1
 * 解释： 在这种情况下，不可能旋转多米诺牌使一行的值相等。
 *
 * @author Jisheng Huang
 * @version 20250503
 */
public class MinDominoRotations_1007 {
    /**
     * Return min number of rotations if one could make all elements in A or B equal to x, else return -1
     *
     * @param A the given top array
     * @param B the given bottom array
     * @return minimum number of rotations to make elements all the same
     */
    public static int minDominoRotations(int[] A, int[] B) {
        int n = A.length;
        int rotations = check(A[0], B, A, n);

        // If one could make all elements in A or B equal to A[0]
        if (rotations != -1 || A[0] == B[0]) {
            return rotations;
        } else {
            // If one could make all elements in A or B equal to B[0]
            return check(B[0], B, A, n);
        }
    }

    /**
     * Helper method to check whether can make all the elements in the array same
     *
     * @param x the given integer
     * @param A the given first array
     * @param B the given second array
     * @param n the length of the array
     * @return number of rotations to make the array elements same for two arrays
     */
    private static int check(int x, int[] A, int[] B, int n) {
        // how many rotations should be done
        // to have all elements in A equal to x
        // and to have all elements in B equal to x
        int rotations_a = 0;
        int rotations_b = 0;

        for (int i = 0; i < n; ++i) {
            // rotations couldn't be done
            if (A[i] != x && B[i] != x) {
                return -1;
            } else if (A[i] != x) {
                // A[i] != x and B[i] == x
                ++rotations_a;
            } else if (B[i] != x) {
                // A[i] == x and B[i] != x
                ++rotations_b;
            }
        }

        return Math.min(rotations_a, rotations_b);
    }

    public static void main(String[] args) {
        int[] top = {2, 1, 2, 4, 2, 2};
        int[] bottom = {5, 2, 6, 2, 3, 2};

        int ans = minDominoRotations(top, bottom);

        System.out.println(ans);

        top = new int[]{3, 5, 1, 2, 3};
        bottom = new int[]{3, 6, 3, 3, 4};

        ans = minDominoRotations(top, bottom);

        System.out.println(ans);
    }
}
